home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 051-075 / disk_075 / diff / diff.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  5KB  |  293 lines
  1. /* diff  --  author Erik Baalbergen */
  2.  
  3. /* Poor man's implementation of diff(1)
  4.  - no options available
  5.  - may give more output than other diffs, due to the straight-forward algorithm
  6.  - runs out of memory if the differing chunks become too large
  7.  - input line length should not exceed LINELEN; longer lines are truncated,
  8.    while only the first LINELEN characters are compared
  9.  
  10.  Please report bugs and suggestions to erikb@cs.vu.nl
  11. */
  12. #include <stdio.h>
  13.  
  14. #define LINELEN 128
  15.  
  16. char *prog;
  17. int diffs = 0;
  18.  
  19. main(argc, argv)
  20.     char **argv;
  21. {
  22.     FILE *fp1 = NULL, *fp2 = NULL;
  23.  
  24.     prog = *argv++;
  25.     if (argc != 3)
  26.         fatal("use: %s file1 file2", prog);
  27.     if (strcmp(argv[0], "-") == 0)
  28.         fp1 = stdin;
  29.     else
  30.     if (strcmp(argv[1], "-") == 0)
  31.         fp2 = stdin;
  32.     if (fp1 == NULL && (fp1 = fopen(argv[0], "r")) == NULL)
  33.         fatal("can't read %s", argv[0]);
  34.     if (fp2 == NULL && (fp2 = fopen(argv[1], "r")) == NULL)
  35.         fatal("can't read %s", argv[1]);
  36.     diff(fp1, fp2);
  37.     exit(diffs > 0);
  38. }
  39.  
  40. fatal(fmt, s)
  41.     char *fmt, *s;
  42. {
  43.     fprintf(stderr, "%s: ", prog);
  44.     fprintf(stderr, fmt, s);
  45.     fprintf(stderr, "\n");
  46.     exit(2);
  47. }
  48.  
  49. /* the line module */
  50. char *malloc();
  51. char *fgets();
  52.  
  53. struct line {
  54.     struct line *l_next;
  55.     char l_text[LINELEN + 2];
  56. };
  57.  
  58. struct line *freelist = 0;
  59.  
  60. struct line *
  61. new_line()
  62. {
  63.     register struct line *l;
  64.  
  65.     if (l = freelist)
  66.         freelist = freelist->l_next;
  67.     else
  68.     if ((l = (struct line *)malloc(sizeof(struct line))) == 0)
  69.         fatal("out of memory");
  70.     return l;
  71. }
  72.  
  73. free_line(l)
  74.     register struct line *l;
  75. {
  76.     l->l_next = freelist;
  77.     freelist = l;
  78. }
  79.  
  80. #define equal_line(l1, l2) (strcmp((l1)->l_text, (l2)->l_text) == 0)
  81.  
  82. struct line *
  83. read_line(fp)
  84.     FILE *fp;
  85. {
  86.     register struct line *l = new_line();
  87.     register char *p;
  88.     register int c;
  89.  
  90.     (p = &(l->l_text[LINELEN]))[1] = '\377';
  91.     if (fgets(l->l_text, LINELEN + 2, fp) == NULL) {
  92.         free_line(l);
  93.         return 0;
  94.     }
  95.     if (p[1] != '\377' && *p != '\n') {
  96.         while ((c = fgetc(fp)) != '\n' && c != EOF) {}
  97.         *p++ = '\n';
  98.         *p = '\0';
  99.     }
  100.     l->l_next = 0;
  101.     return l;
  102. }
  103.  
  104. /* file window handler */
  105. struct f {
  106.     struct line *f_bwin, *f_ewin;
  107.     struct line *f_aside;
  108.     int f_linecnt;    /* line number in file of last advanced line */
  109.     FILE *f_fp;
  110. };
  111.  
  112. advance(f)
  113.     register struct f *f;
  114. {
  115.     register struct line *l;
  116.     
  117.     if (l = f->f_bwin) {
  118.         if (f->f_ewin == l)
  119.             f->f_bwin = f->f_ewin = 0;
  120.         else
  121.             f->f_bwin = l->l_next;
  122.         free_line(l);
  123.         (f->f_linecnt)++;
  124.     }
  125. }
  126.  
  127. aside(f, l)
  128.     struct f *f;
  129.     struct line *l;
  130. {
  131.     register struct line *ll;
  132.  
  133.     if (ll = l->l_next) {
  134.         while (ll->l_next)
  135.             ll = ll->l_next;
  136.         ll->l_next = f->f_aside;
  137.         f->f_aside = l->l_next;
  138.         l->l_next = 0;
  139.         f->f_ewin = l;
  140.     }
  141. }
  142.  
  143. struct line *
  144. next(f)
  145.     register struct f *f;
  146. {
  147.     register struct line *l;
  148.  
  149.     if (l = f->f_aside) {
  150.         f->f_aside = l->l_next;
  151.         l->l_next = 0;
  152.     }
  153.     else
  154.         l = read_line(f->f_fp);
  155.     if (l) {
  156.         if (f->f_bwin == 0)
  157.             f->f_bwin = f->f_ewin = l;
  158.         else {
  159.             f->f_ewin->l_next = l;
  160.             f->f_ewin = l;
  161.         }
  162.     }
  163.     return l;
  164. }
  165.  
  166. init_f(f, fp)
  167.     register struct f *f;
  168.     FILE *fp;
  169. {
  170.     f->f_bwin = f->f_ewin =  f->f_aside = 0;
  171.     f->f_linecnt = 0;
  172.     f->f_fp = fp;
  173. }
  174.  
  175. update(f, s)
  176.     register struct f *f;
  177.     char *s;
  178. {
  179.     register char c;
  180.  
  181.     while (f->f_bwin && f->f_bwin != f->f_ewin) {
  182.         printf("%s%s", s, f->f_bwin->l_text);
  183.         advance(f);
  184.     }
  185. }
  186.     
  187. /* diff procedure */
  188. diff(fp1, fp2)
  189.     FILE *fp1, *fp2;
  190. {
  191.     struct f f1, f2;
  192.     struct line *l1, *s1, *l2, *s2;
  193.     register struct line *ll;
  194.  
  195.     init_f(&f1, fp1);
  196.     init_f(&f2, fp2);
  197.     l1 = next(&f1);
  198.     l2 = next(&f2);
  199.     while (l1 && l2) {
  200.         if (equal_line(l1, l2)) {
  201. equal:
  202.             advance(&f1);
  203.             advance(&f2);
  204.             l1 = next(&f1);
  205.             l2 = next(&f2);
  206.             continue;
  207.         }
  208.         s1 = l1;
  209.         s2 = l2;
  210.         /* start searching */
  211. search:
  212.         if ((l2 = next(&f2)) == 0)
  213.             continue;
  214.         ll = s1;
  215.         do {
  216.             if (equal_line(ll, l2)) {
  217.                 aside(&f1, ll);
  218.                 differ(&f1, &f2);
  219.                 goto equal;
  220.             }
  221.         } while (ll = ll->l_next);
  222.         if ((l1 = next(&f1)) == 0)
  223.             continue;
  224.         ll = s2;
  225.         do {
  226.             if (equal_line(ll, l1)) {
  227.                 aside(&f2, ll);
  228.                 differ(&f1, &f2);
  229.                 goto equal;
  230.             }
  231.         } while (ll = ll->l_next);
  232.         goto search;
  233.     }
  234.     /* one of the files reached EOF */
  235.     if (l1) /* eof on 2 */
  236.         while (next(&f1)) {}
  237.     if (l2)
  238.         while (next(&f2)) {}
  239.     f1.f_ewin = 0;
  240.     f2.f_ewin = 0;
  241.     differ(&f1, &f2);
  242. }
  243.  
  244. differ(f1, f2)
  245.     register struct f *f1, *f2;
  246. {
  247.     int cnt1 = f1->f_linecnt, len1 = wlen(f1), cnt2 = f2->f_linecnt,
  248.         len2 = wlen(f2);
  249.  
  250.     if ((len1 = wlen(f1)) || (len2 = wlen(f2))) {
  251.         if (len1 == 0) {
  252.             printf("%da", cnt1);
  253.             range(cnt2 + 1, cnt2 + len2);
  254.         }
  255.         else
  256.         if (len2 == 0) {
  257.             range(cnt1 + 1, cnt1 + len1);
  258.             printf("d%d", cnt2);
  259.         }
  260.         else {
  261.             range(cnt1 + 1, cnt1 + len1);
  262.             putchar('c');
  263.             range(cnt2 + 1, cnt2 + len2);
  264.         }
  265.         putchar('\n');
  266.         if (len1)
  267.             update(f1, "< ");
  268.         if (len1 && len2)
  269.             printf("---\n");
  270.         if (len2)
  271.             update(f2, "> ");
  272.         diffs++;
  273.     }
  274. }
  275.  
  276. wlen(f)
  277.     struct f *f;
  278. {
  279.     register cnt = 0;
  280.     register struct line *l = f->f_bwin, *e = f->f_ewin;
  281.  
  282.     while (l && l != e) {
  283.         cnt++;
  284.         l = l->l_next;
  285.     }
  286.     return cnt;
  287. }
  288.  
  289. range(a, b)
  290. {
  291.     printf(((a == b) ? "%d" : "%d,%d"), a, b);
  292. }
  293.